package code.AlgorithmInterview.chapter8;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Tree01 {
   Map<String, String> phone = new HashMap<String, String>(){{
       put("2", "abc");
       put("3", "def");
       put("4", "ghi");
       put("5", "jkl");
       put("6", "mno");
       put("7", "pqrs");
       put("8", "tuv");
       put("9", "wxyz");
   }};
    List<String> output = new ArrayList<>();

    private  void backtrack(String res,String digit){
        if(digit.length() == 0){
            output.add(res);
        }
        else {
            String number = digit.substring(0,1);
            String letters = phone.get(number);
            for (int i = 0; i < letters.length(); i++) {
                String letter = letters.substring(i,i+1);
                backtrack(res+letter,digit.substring(1));
            }
        }
    }
    public  List<String> letterCombinations(String digits) {
        if(digits.length() != 0)
            backtrack("",digits);
        return output;
    }

}
